As a direct result of microcomputers and word processing systems, many computer output devices that accept digital data and produce hardcopy output have been developed. A large fraction of these devices now use non-impact printing methods, such as ink jet or laser printing. These machines are faster and quieter than impact printers with resolution that is sufficient for letter quality printing.
In a related technology, as the cost of charged coupled device (CCD) image scanning arrays decreases, one can expect the present type of analog photocopying machine to evolve to a more general purpose machine that will digitize the document by scanning to divide the image on the document into picture elements or pixels and provide a digital value that is one of many possible levels for each pixel and then print using the digital data. In addition, the digital data is available for the computer and the computer can output data directly to the print mechanism. This is just one example of new technologies that use digital data.
Using a general purpose computer, digital enhancement techniques can be applied to improve the perceived quality of the image produced from digital signals which define the density of each image element or pixel using as many as, but not limited to, 256 levels. This is not commercially practiced, as the computational load to enhance the document is too time consuming or expensive making it necessary to simplify the algorithms used to reduce the computational loads. A digital document can require upwards of 15 million picture elements (pixels) to define it, so minutes to hours would be needed to enhance the document on a general purpose computer. Specialized image enhancement computers are available, but at a cost of tens to hundreds of thousands of dollars.
In all image forming systems, degradation of the original information occurs which normally manifests itself in two forms--(1) blurring of edges (reduced resolution, lower sharpness) and (2) random irregularities (noise, fog). In normal photographic images it has long been known that edge sharpness can be enhanced and noise reduced by masking the original with a negative unsharp mask of suitable contrast (usually lower than that of the original). Early work by J. A. C. Yule is representative of this photographic masking approach (U.S. Pat. Nos. 2,407,211; 2,420,636; 2,455,849) and more complex approaches are represented by Blearson et al in U.S. Pat. No. 3,615,433. An early attempt to use a raster scan of the image while measuring the instantaneous light values photoelectrically and attenuating the beam according to a predetermined relationship with the light value is disclosed by Folse in U.S. Pat. No. 3,011,395. The rapid development of the Space Program has resulted in the emergence of high efficiency digital means of digitizing, analyzing, reconstituting and enhancing images. Median filtering as a means of enhancing edge contrast has also been studied (e.g. B. R. Frieden JOSA 66. 280- 283 (1976)). In the medical radiography field this stimulated the development of computerized tomography and the digital processing of radiographs in general (S. R. Amtey et al, SPIE 207, 210-211 (1979), and C. R. Wilson et al, SPIE 314, 327-330 (1981)). In these approaches the image has been divided into a large number of pixels by scanning A moving window, consisting of n.times.m pixels centered on pixel i with image value D.sub.i, is investigated by an on-line computer as pixels i are scanned. The mean or arithmetic average D of the pixels within the window is then used to modify the central pixel value D.sub.i to a filtered value D.sub.i ' by the algorithm: EQU D.sub.i '=aD.sub.i -bD
The parameters a and b are chosen to give specific image characteristics, but are constant over the scan of a single image.
The concept of varying parameters similar to a and b throughout the scan of the image based on certain local properties of the image has been studied and several patents (H. Kato et al U.S. Pat. Nos. 4,315,318 and 4,317,179 and M. Ishida et al U.S. Pat. No. 4,346,409) have disclosed particular relationships between the parameters and the values of D.sub.i or D which can give further image enhancement. These techniques do not, however, distinguish between noise and image edges as far as enhancement is concerned, and the higher the image value D.sub.i or D, the greater the enhancement. In other technology areas, similar approaches have been made. Thus in E. Alparslau and F. Ince IEEE Vol. SMC-11, 376-384 (1981) images are treated with an edge enhancement algorithm based in part on an adaptive parameter determined by the difference between the maximum and minimum pixel values in the window at any point. U.S. Pat. No. 4,334,244 discloses an image enhancement system wherein a running average of a group of digitized samples of a video signal and a median of a group of digitized samples are processed to provide a gradient sample. The gradient sample is scaled according to the noise level of the video signal. The scaled sample gradient is multiplied by the difference between the median and running average samples and added to the average sample to generate an output sample. The output samples are converted into an enhanced video signal. It is known also that analog photographic images can be modified. They can be enlarged, combined, and have the contrast in some areas enhanced and in other areas reduced (smoothed). These same results can be achieved by the digital processing of digital images. In addition, digital image processing can modify images in many important ways that analog processing can not. Edge enhancement, noise filtering, gray scale stretching or compressing, and color correction are a few of the techniques available to digitally improve the perception of an image.
It is known that an image with accentuated edges is often more subjectively pleasing for viewing since it can increase the visual depth perception and in some cases provide more information. Since sharpness is an effect associated with edges, a method that isolates and amplifies edges is needed. Edges represent high frequency components of the image; that is, regions where the intensity of the image is changing more rapidly have higher spatial frequencies. Conversely regions where the image is changing slowly have only low spatial frequencies present.
One known method to extract the high frequency components of the signal is to subtract the low frequency components from the original signal. The resulting high pass filter can be constructed by suitably combining an all pass filter and a low pass filter, as EQU High Pass Filter=All Pass Filter--Low Pass Filter. (1.1)
Once isolated, the resulting high frequency components can be scaled by multiplying the filter by a factor (k): EQU k.times.High Pass=k.times.All Pass--k.times.Low Pass. (1.2)
The resulting filter provides image data which has been stripped of the original low frequency components and then must be added back to the image data. This results in an unsharp masking enhancement filter (USM) which can be represented by: EQU USM=k.times.All Pass-k.times.Low Pass 30 Low Pass; or (1.3) EQU USM=k.times.All Pass--(k-1).times.Low Pass. (1.4)
Operating repeatedly on the image data with this filter in a prescribed manner will yield enhanced image data.
The foregoing unsharp masking enhancement filter is used by A. B. Mahmoodi and Owen L. Nelson in their U.S. Pat No. 4,571,635, wherein a sliding window, which moves across the image pixel signals in both vertical and horizontal directions, is used to apply the filter to the image pixel signals. Operating on the level or value of the center pixel, D.sub.c, of the window as the all pass filter value and using the mean level or value, D, as the low value with D.sub.c ', representing the unsharp masking filter value, equation 1.4 can be written as EQU D.sub.c '=kD.sub.c -(k-1)D (2.1)
which is the form for equation (2.4) in U.S. Pat. No. 4,571,635 Mahmoodi et al after it is corrected. The error in equation (2.4) of the patent is due to an error in the expression appearing in column 5, line 30 of the patent which is used to arrive at equation (2.4) of the patent. Line 30 Line 30 indicates b/1-b=1-k, which should -b/1-b=1-k.
Rearranging equation 2.1, it can be written as EQU D.sub.c '=k(D.sub.c -D)+D (2.2)
U.S. Pat. No. 4,571,635 to Mahmoodi et al makes the coefficient k adaptive to change in the image scene. Where an edge is crossed, emphasis is desired (large coefficient k) to perform the image edge and contrast enhancement. In areas with no edges the emphasis coefficient is kept to a low level to minimize high spatial frequency noise and smooth the image. The algorithm of the patent controls the emphasis coefficient k with a statistical parameter that can be calculated for the window at any given position. The standard deviation, .sigma., of the pixel values within the window is used to produce a function f(.sigma.) which is suitable for the determination of k.
Low cost, high speed implementation of the algorithm disclosed in U.S. Pat. No. 4,571,635 to Mahmoodi et al is difficult due to the large number of calculations involved for each pixel signal, the amount of memory image signals required and the lack of specialized integrated circuits currently available. The lack of specialized integrated circuits capable of spatial image processing, as is described in U.S. Pat. No. 4,571,635 means that complex imaging processing algorithms must be carried out by the use of many low level circuit elements. While this results in the use of simple algorithms many circuit boards are required along with bulky power supplies and complicated interconnects. The complexity and cost of implementing the algorithm as disclosed in U.S. Pat. No. 4,571,635 presents a cost/benefit ratio that impedes its possible use in many digital acquisition, transmission or reproduction devices as television sets, microfilm reader/printers, copy machines, facsimile machines, optical character readers and digital still photography cameras. It will be noted that in Example 4 set forth in U.S. Pat. No. 4,571,635 a Digital Equipment Corporation VAX 11/750 computer was used to run a program for an image enhancement process according to the algorithm disclosed in the patent.
One barrier to the practical implementation in hardware of the algorithm as set forth in equation (2.2) is the computational difficulty that is encountered with respect to obtaining the mean level or value D for each window. This mean or average for the window is the result obtained by multiplying the center pixel and the surrounding pixels by one, totaling such results, and dividing by the number of pixels in the window, e.g., dividing by nine in the case of a 3.times.3 window. Thus, for a 3.times.33 window ##EQU2## where D.sub.i is the value of the pixel at the various nine locations of a 3.times.3 window.
The primary disadvantages in the implementation of the mean equation (3.1) are the division by 9 and the method of calculating the mean or average. The traditional method of dividing by an arbitrary number would involve the development of a special processor to handle the division. This solution is expensive for it involves too much circuitry or consumes too many clock cycles to be of value.
The simplest method of calculating the mean according to equation (3.1) involves holding all nine numbers in memory and adding them one at a time to an intermediate register. When the sum has been accumulated, it is transferred to a divider. The disadvantages in this scheme are: that all numbers must be stored in a register until the sum is generated which requires more bits for representation, and hence the complexity of the adder increases, and division by nine is still necessary.
Another method of calculating the mean according to equation (3.1) would be to sum the numbers in stages. The first stage adds eight elements in pairs with four adders, carrying the last one. The output of this first stage has one more bit than the input. The second stage then sums four of the five remaining numbers, carrying the fifth, and again the output word length has grown by one bit. This continues for four stages of adders, with the final word size four bits larger than the largest input word. The output of the fourth stage is again passed to divide by nine processor. This pipeline method is faster in that as soon as the first stage has finished operating on the input and passed the results to the second stage, it is free to process the next window. The disadvantages are that eight adders are necessary, and at each stage the adders complexity has to increase to handle the progressively larger word size, and one is still faced with the divide by nine problem.
Another barrier to a practical implementation in hardware of the algorithm as set forth in equation (2.2) is the difficulty in implementing the computation of the standard deviation of the pixel value for an image window of arbitrary size which is used for a determination of the coefficient k in the equation.
The standard deviation of an image window gives a measure of the amount of spread of the image window from the mean of the window. In the image processing area this is also a measure of the high frequency components in the image window. In the context of unsharp masking, as in U.S. Pat. No. 4,571,635, the standard deviation and its size regulates the amount of amplification (coefficient k) a given pixel receives.
Currently there are two solutions to the problem of real time calculations of this magnitude. The first solution involves the programming of an expensive computer to perform the necessary calculations. The second solution involves fabricating a dedicated circuit board set to implement the calculation. By cascading several stages of multipliers and accumulators followed by dividers and a block for the square root the standard deviation calculation can be reduced to a few circuit boards. This solution is also costly to implement and integrate into the unsharp masking algorithm.